package search;

import sort.Sort;

import java.util.Arrays;

/**
 * 无序数组，查找第K大的值
 *
 * @author cooper
 * @date 2019-07-15
 */
public class FindMaxKValueSearch extends BaseSearch {

    /**
     * 排序之后查找
     *
     * @param array 待查找的数组
     * @param k     索引K
     * @return 数组中第K大的值
     */
    public Integer find1(int[] array, int k) {

        if (k < 0 || array == null || k > array.length) {
            return null;
        }

        Sort.quickSort(array);
        System.out.println("排序后的结果: "+ Arrays.toString(array));

        return array[array.length-k];
    }

    /**
     * 维护一个长度为k的数组
     *
     * @param array 待查找的数组
     * @param k     索引K
     * @return 数组中第K大的值
     */
    public Integer find2(int[] array, int k) {
        if (k < 0 || array == null || k > array.length) {
            return null;
        }

        int[] help = new int[k];
        System.arraycopy(array, 0, help, 0, k);

        for (int i = k; i < array.length; i++) {
            compareAndSwap(help, array[i]);
        }

        //返回数组help的最小值
        int min = Integer.MAX_VALUE;
        for (int value : help) {
            if (min > value) {
                min = value;
            }
        }
        return min;
    }

    private void compareAndSwap(int[] help, int value) {
        //找出help数组的最小值min和最小值的索引index，如果value > min，help[index] = value
        int min = Integer.MAX_VALUE;
        int index = 0;
        for (int i = 0; i < help.length; i++) {
            if (min > help[i]) {
                min = help[i];
                index = i;
            }
        }
        if (value > min) {
            help[index] = value;
        }
    }

    /**
     * 二叉堆计算
     *
     * @param array 待查找的数组
     * @param k     索引K
     * @return 数组中第K大的值
     */
    public Integer find3(int[] array, int k) {
        if (k < 0 || array == null || k > array.length) {
            return null;
        }

        //help数组是一个长度为k的二叉堆 最小堆
        int[] help = new int[k];
        System.arraycopy(array, 0, help, 0, k);

        buildHeap(help);
        for (int i = k; i < array.length; i++) {
            int top = help[0];
            if (array[i] > top){
                help[0] = array[i];
                downerAdjust(help, 0);
            }
        }
        return help[0];
    }

    /**
     * @param array
     */
    private void buildHeap(int[] array) {
        // 从最后一个非叶子节点开始，依次下沉调整
        for (int i = array.length / 2; i >= 0; i--) {
            downerAdjust(array, i);
        }
    }

    /**
     * 上浮调整
     *
     * @param help
     */
    private void upperAdjust(int[] help) {
        //数组最后一个节点
        int childIndex = help.length - 1;
        //节点的父节点
        int parentIndex = (childIndex - 1) >> 1;

        int temp = help[childIndex];

        while (childIndex > 0 && temp < help[parentIndex]) {
            help[childIndex] = help[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) >> 1;
        }
        help[parentIndex] = temp;
    }

    /**
     * 下沉操作
     *
     * @param array    待调整的数组
     * @param curIndex 要下沉的节点
     */
    private void downerAdjust(int[] array, int curIndex) {
        int temp = array[curIndex];//临时保存

        int childIndex = 2 * curIndex + 1;
        while (childIndex < array.length) {
            // 如果有右孩子，而且右孩子小于左孩子，则下沉到右孩子
            if (childIndex + 1 < array.length && array[childIndex] > array[childIndex + 1]) {
                childIndex++;
            }
            if (temp < array[childIndex]) {
                break;
            }
            array[curIndex] = array[childIndex];
            curIndex = childIndex;
            childIndex = 2* childIndex + 1;
        }
        array[curIndex] = temp;

    }

}
